package com.liyunhan.GreedyAlgorithm;

/**
 * @Description: 贪心算法
 * 一个汽车加满油后可行驶n公里, 由起点a到起点b为m公里.汽车出发时加满了油, 途中设有
 * k个加油站, d1是第一个加油站距起点的距离, di是第i个加油站距其前一个加油站的距离.
 * 设计一个算法, 求出加油方案, 使得加油次数最少即可到达终点.
 * 本算法设定在起点汽车加满油一次 --> 即在第一个加油站加油一次
 * @Author: Liyunhan
 * @Date: 2021/12/8 23:09
 */
public class OilingCar {
    //k个加油站
    private int k;
    //加满油可行驶n公里
    private double n;
    //每个加油站之间的距离(k个加油站, 第一个加油站是起点, 所以di是第i个加油站距其前一个加油站的距离)
    //共有k-1个距离
    private double[] d;
    //需要加油的次数
    private int count = 0;

    /**
     * 算法要求必须输入k, n, d, 故不提供无参构造器
     *
     * @param k
     * @param n
     * @param d
     */
    public OilingCar(int k, double n, double[] d) {
        this.k = k;
        this.n = n;
        this.d = d;
        //检查"合理性", 如果任意相邻两个加油站的距离大于行驶的最大距离n, 则输出无解
        for (int i = 0; i < d.length; i++) {
            if (d[i] > n) {
                System.out.println("无解!");
                System.exit(0);
            }
        }
    }

    /**
     * 算法主实现
     * 每次开到尽量远的加油站加油，也就是说不得不加油的时候。
     * 如：到了一个加油站正好没油，或者到了一个加油站不加油，剩余油就不够开到下一个加油站
     *
     * @return
     */
    public int mainAlgorithm() {
        //汽车出发, 算法规定在起点汽车加满油一次 --> 即在第一个加油站加油一次
        count++;
        //记录汽车某次加满油后行驶的距离
        double distance = 0;
        //开始模拟(已经做过"合理性判断")
        for (int i = 0; i < k; i++) {
            distance += d[i];
            if (distance > n) {
                //需要加油
                count++;
                //以当前加油站到下一个加油站的距离为起始距离, 判断这次加满油 -->下次到加油站需不需要加油
                distance = d[i];
            }
        }

        return count;
    }

    public int getCount() {
        return count;
    }

    public void setCount(int count) {
        this.count = count;
    }
}
